package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param root TreeNode类
 * @return int整型
 */
var res int = -1e10

func maxPathSum(root *TreeNode) int {
	// write code here
	getMaxPathSum(root)
	return res
}

func getMaxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftMax := max(0, getMaxPathSum(root.Left))
	rightMax := max(0, getMaxPathSum(root.Right))

	res = max(res, root.Val+max(leftMax+rightMax, max(leftMax, rightMax)))

	return max(leftMax, rightMax) + root.Val
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
